//颜色分类
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1;
        int right = n;
        int i = 0;
        while (i < right) {
            if (nums[i] < 1)
                swap(nums[i++], nums[++left]);
            else if (nums[i] == 1)
                i++;
            else
                swap(nums[i], nums[--right]);
        }
        return;
    }
};

//杨辉三角
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 1; i <= numRows; i++) {
            vector<int> path(i);
            for (int j = 0; j < i; j++) {
                if (j == 0 || j == i - 1) {
                    path[j] = 1;
                } else {
                    path[j] = ret[i - 2][j - 1] + ret[i - 2][j];
                }
            }
            ret[i - 1] = path;
        }
        return ret;
    }
};

//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int ret = 1;
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
                ret = max(ret, dp[i]);
            }
        }
        return ret;
    }
};